package sort

// 归并排序
func mergeSort(arr []int) {
    tmpInt := make([]int, len(arr))
    msort(arr, tmpInt, 0, len(arr)-1)
}

func msort(arr, tmpArr []int, left, right int) {
    if left < right {
        mid := (left + right) / 2
        msort(arr, tmpArr, left, mid)
        msort(arr, tmpArr, mid+1, right)
        merge(arr, tmpArr, left, mid, right)
    }
}

func merge(arr, tmpArr []int, left, mid, right int) {
    lPos := left
    rPos := mid + 1
    pos := left
    for {
        if lPos > mid || rPos > right {
            break
        }

        if arr[lPos] <= arr[rPos] {
            tmpArr[pos] = arr[lPos]
            pos++
            lPos++
        } else {
            tmpArr[pos] = arr[rPos]
            pos++
            rPos++
        }
    }

    for i := lPos; i <= mid; i++ {
        tmpArr[pos] = arr[i]
        pos++
    }

    for i := rPos; i <= right; i++ {
        tmpArr[pos] = arr[i]
        pos++
    }

    for i := left; i <= right; i++ {
        arr[i] = tmpArr[i]
    }
}
